/*
提交链接:https://leetcode.cn/problems/maximum-difference-score-in-a-grid/description/
3148. 矩阵中的最大得分
赖德檀 2024/12/13
*/

class Solution {
public:

    int maxScore(vector<vector<int>>& grid) {
        int ans = INT_MIN;
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
        //例:14-7+7-5 = 14-5,所以dp数组维护的是从(0,0)到(i,j)的最小值
        //比如到达(2,2),只要知道(0,0)到(2,2)最小的值,从该值到达(2,2)即可
        //无论该值在哪,经过下和右的路径能到达该位置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int sum = min(dp[i + 1][j], dp[i][j + 1]);//左/上的最小值
                ans = max(ans, grid[i][j] - sum);
                dp[i + 1][j + 1] = min(sum, grid[i][j]);//更新(i,j)的最小值(起点不定,因为可以从任一单元格移动到另一个位于正下方或正右侧的任意单元格（不必相邻）)

                // for(int i=0;i<n+1;i++)
                // {
                //     for(int j=0;j<m+1;j++)
                //     cout<<dp[i][j]<<" ";
                //     cout<<endl;
                // }
                // cout<<"*******"<<endl;
            }
        }
        return ans;
    }
};